The present invention is generally directed to an apparatus and method that generates, analyzes and graphically displays information descriptive of a physical object, and more particularly to a method and apparatus that provides a topologically consistent visual representation of a three dimensional surface.
An automated measurement system can generate a vast amount of information respecting a characteristic of a physical object under examination. Such information becomes much more useful if it is simplified and presented in an understandable way. Given a measured signal pattern that describes how a characteristic varies spatially within a bounded region, the information provided by the signal pattern can be simplified by selecting a value of the characteristic and then generating a set of all points within the bounded region where the value of the characteristic is equal to the selected value. These points are said to define a three dimensional surface called an "isosurface". This is because the prefix "iso" generally means "same" or "equal" and, at every point on the isosurface, the value of the characteristic equals the selected value. Generating a visual representation of the isosurface on a graphical display device has been found to be a useful way of presenting the information in a simplified, understandable form.
For example, computer aided tomography scanners provide a vast amount of X-Ray attenuation data when a human brain is analyzed. This data becomes much more useful if it is simplified and presented in an understandable way. Given X-Ray attenuation data points that describes how X-Ray absorption by brain tissue spatially varies within the brain, the X-Ray attenuation data can be simplified by selecting a single attenuation value corresponding to a particular tissue absorption level. By selecting an attenuation value that corresponds to X-Ray absorption by a brain tumor's outer layer and generating a set of all points within a region of the brain where attenuation is equal to the selected value, the X-Ray attenuation data can reveal an isosurface corresponding to a brain tumor hidden within the brain. By generating a visual representation of the tumor isosurface on a graphical display, a doctor can see the shape and location of the tumor. The display aids the doctor in determining whether the tumor can be safely removed.
As another example, a measurement system can generate a signal pattern describing various fluid velocities within a fluid flow. The fluid velocity signal pattern can be simplified by selecting a single fluid velocity value that is related to potential generation of undesired turbulent flow. By generating a set of all points within a region of the fluid flow where the fluid velocity is equal to the selected value, the fluid velocity signal pattern can be used to reveal an isosurface corresponding to a fluid velocity layer within the fluid flow. By generating a visual representation of the fluid velocity isosurface on a graphical display, a design engineer can see the shape and location of the fluid velocity layer that leads to undesired turbulent flow. The display aids the design engineer in determining how to alter the fluid flow so as to reduce turbulent flow.
As yet another example, a measurement system can generate a signal pattern describing various temperatures within a nuclear reactor core. The temperature signal pattern can be simplified by selecting a single temperature value that corresponds to a suspected fault condition. By generating a set of all points within a region of the core where the temperature is equal to the selected value, the temperature signal pattern can be used to reveal an isosurface corresponding to a temperature layer within the core. By generating a visual representation of the temperature isosurface on a graphical display, a nuclear engineer can see the shape and location of the temperature layer indicating the fault condition. The display aids the nuclear engineer in determining how to safely shut down the reactor core.
Though it has long been known that isosurfaces are a helpful way of analyzing and displaying information, certain difficulties are associated with their generation and display. In the example of the temperature measurement system discussed above, temperature is measured at spaced apart grid locations that usually do not precisely coincide with the location of the temperature layer of interest. Accordingly, complete knowledge of the isosurface corresponding to the temperature layer is unavailable. In general the isosurface corresponding to the temperature layer lies spatially between measured locations. A technique known as "interpolation" is used to estimate the spatial coordinates of points approximately lying on the isosurface between these measured locations. Thus an "interpolant isosurface" is a three dimensional surface defined by a set of all interpolated points within the bounded region where the value of the characteristic is equal to the selected value. This concept is further illustrated in the following example.
As shown in FIG. 1 twenty seven temperature measurements are taken at spaced apart grid locations within the volume of a reactor core. It is assumed that a 100 degree temperature layer is of particular interest, so a threshold value of 100 degrees is chosen. For the purposes of illustration, as shown in FIG. 1 the measured locations having temperatures greater than 100 degrees are represented by black balls, while measured locations having temperatures less than 100 degrees are represented by white balls. As shown, an interpolant isosurface 1 lies spatially between measured temperature locations. This is so because in this example, none of the measured locations provided a temperature measurement of exactly 100 degrees.
It should be noted from FIG. 1 that the interpolant isosurface partitions the three dimensional signal pattern into pattern groupings 2 and 3. More particularly in this example, the interpolant isosurface partitions the three dimensional signal pattern into just two pattern groupings. Pairs of adjacent measurement points that are part of the same pattern grouping are shown in FIG. 1 as being connected by heavily drawn lines. Pairs of adjacent measurement points that are not part of the same pattern grouping are shown in FIG. 1 as being connected by thinly drawn lines. Such partitioning of the three dimensional signal pattern by the interpolant isosurface is of great importance in defining the topology of the isosurface and will be discussed in greater detail later in the present application.
It has previously been known that one method of generating a visual representation of an interpolant isosurface is to interpolate a large number of point elements and then display the point elements on a graphics display device. This method is substantially similar to the method taught in U.S. Pat. No. 4,719,585 entitled "Dividing Cubes System and Method for the Display of Surface Structures Contained Within the Interior Region of a Solid Body" by Cline et al. Because Cline ('585) provides helpful background information on the difficulties of generating and displaying interpolant isosurfaces, Cline ('585) is incorporated here by reference. The dividing cubes method interpolates a number of point elements corresponding to a number of pixel display elements on the graphical display device. Thus the number of point elements matches the resolution of the graphical display device. Currently, high resolution display devices offer resolutions of 1280 by 1024 pixels. As might be expected, interpolating such a large number of point elements creates a tremendous computational burden. A less complex display requiring fewer interpolated points is desirable to ease this computational burden.
It is computationally less burdensome and more efficient to use a method known as a "piecewise polygonal approximation" to generate a visual representation of the interpolant isosurface. Such an approximation to the interpolant isosurface is created by computing coordinates of a set of points, called a set of polygon vertex points, which lie on the interpolant isosurface between pairs of adjacent grid locations where the characteristic of the physical object is measured.
The set of polygon vertex points are then interconnected to from a network of polygons, the polygon vertex points being vertices of the network of polygons. This method is known as a piecewise polygonal approximation because the network of polygons approximate the interpolant isosurface. The network of polygons is then used to generate the visual representation of the interpolant isosurface on the graphical display device.
Methods that generate the piecewise polygonal approximation to the interpolant isosurface are described in two other patents issued to Cline et al. One is U.S. Pat. No. 4,729,098 entitled "System and Method Employing Nonlinear Interpolation for the Display of Surface Structures Contained Within the Interior Region of a Solid Body". The other is U.S. Pat. No. 4,710,876 entitled "System and Method for the Display of Surface Structures Contained Within the Interior Region of a Solid Body". Because Cline ('098) and Cline ('876) both provide helpful background information on the difficulties of generating visual representations of interpolant isosurfaces, both patents are incorporated here by reference. The polygon vertex points discussed previously herein are referred to more generally at some parts of both Cline ('098) and Cline ('876) simply as vertex points, though such vertex points are still discussed in these patents in the context of polygonal or triangular surfaces.
The display generated by piecewise polygonal approximation is of low complexity because a small number of interpolated points are used in defining the network of polygons. Such low complexity allows efficient use of computational resources. Despite these positive attributes, previously known methods of generating piecewise polygonal approximations have serious shortcomings.
The problem of "topological consistency" arises in constructing piecewise polygonal approximations because certain groups of polygon vertex points present an ambiguity as to how they are to be interconnected to form the network of polygons. The ambiguity may be resolved in numerous "ad hoc" ways since there are numerous possible ways of interconnecting the polygon vertex points. However for a given signal pattern, only one way of linking such groups of polygon vertex points will produce a piecewise polygonal approximation that is topologically consistent with an interpolant isosurface determined by a particular threshold value. The term "topologically consistent" is defined in the following context: to say that the piecewise polygonal approximation is topologically consistent with the interpolant isosurface means that the piecewise polygonal approximation partitions the three dimensional signal pattern into the same pattern groupings as does the interpolant isosurface.
Cline ('098) and Cline ('876) employ ad hoc methods, yielding piecewise polygonal approximations that are not always topologically consistent with the interpolant isosurface. This creates undesirable results because the display of a topologically inconsistent piecewise polygonal approximation includes anomalous surface features that are not present in the interpolant isosurface. As might be expected, such anomalous surface features tend to attract the interest and mental focus of a person viewing the graphical display. In this way, the anomalous surface features confuse and mislead the person viewing the display. Even more confusion is created because such anomalous surface features do not appear at all levels of display refinement. The anomalous surface features can appear when a coarse piecewise polygonal approximation is displayed on the graphical display device, but then they can disappear when a refined piecewise polygonal approximation is displayed on the graphical display device. This type of problem is highlighted in the following example.
For the sake of this example it will be said that a surgical patient's brain is being examined by the CAT scan machine discussed earlier. The interpolant isosurface of interest corresponds to the outer layer of a brain tumor, and an ad hoc method is used to generate coarse and refined piecewise polygonal approximations of the interpolant isosurface of interest. FIG. 2A shows a coarse graphical display 100 generated by displaying the coarse polygonal approximation of the interpolant isosurface on a graphics display device. The coarse graphical display is viewed by a doctor who is striving to determine whether the shape and location of the brain tumor will allow safe surgical removal. The doctor notices what appears to be an interesting surface feature as depicted by a particular portion 102 of the coarse display 100. The doctor commands the system to "zoom in" on this feature. In response to the doctor's command, the system generates additional polygon vertex points and interconnects the additional polygon vertex points, thereby producing the refined polygonal approximation and an expanded display 103 of the feature under study, as shown in FIG. 2B. Whereas the portion 102 of the coarse display 100 suggested a protruding-peninsular shaped extension feature 104 of the tumor, the expanded display 103 shows a smaller tumor having a rounded end 105 and a small, disconnected island 106 some distance apart from the rest of the tumor. This is confusing to the doctor, because the interesting surface feature has transformed in an unexpected way. As this example illustrates, ad hoc methods can produce coarse polygonal approximations and refined polygonal approximations that have different topologies. If the coarse polygonal approximation and the refined polygonal approximation were each topologically consistent with the interpolant isosurface, then the confusion discussed previously would be avoided.
The above discussions have generally outlined the difficulties of generating visual representations of an interpolant isosurface. As discussed previously, the method disclosed in Cline ('585) does not produce a visual representation having low complexity. Methods disclosed in Cline ('098) and ('876) do not produce visual representations that arc always topologically consistent with the interpolant isosurface. In summary, what is needed is a method for displaying an interpolant isosurface by generating a visual representation that is of low complexity, and topologically consistent with the isosurface.